package linkedList.递归;

import linkedList.BaseLinkedListTest;
import po.ListNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 删除排序链表中的重复元素II82.java
 * @Description TODO https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
 * @createTime 2021年03月10日 17:01:00
 */
public class 删除排序链表中的重复元素II82 extends BaseLinkedListTest {

    public static void main(String[] args) {
        //deleteDuplicates(createLinkedList(1, 1));
        deleteDuplicatesTwo(createLinkedList(1, 2, 3, 3,4, 4,5));
    }

    /**
     * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
     */
    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        if (head.val == head.next.val) {
            while (head.next != null && head.val == head.next.val) {
                head = head.next;
            }
            return deleteDuplicates(head.next);
        } else {
            head.next = deleteDuplicates(head.next);
        }
        return head;
    }

    public static ListNode deleteDuplicatesTwo(ListNode head) {
        ListNode pre = new ListNode();
        pre.next = head;
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode p1 = pre, p2 = head, tmp = pre;
        boolean firstCircle = true;
        while (p2 != null) {
            //如果p1=p2，就把p1执行p2的下一个节点，然后p2往后移动
            if (p1.val == p2.val) {
                if (firstCircle) {
                    if (p2.val != p2.next.val) {
                        firstCircle = false;
                        tmp = p1;
                        p1 = p1.next;
                        p2 = p2.next;
                        continue;
                    }

                }
                while (p2.next != null && p1.val == p2.next.val) {
                    p2 = p2.next;
                }
                tmp.next = p2.next;
                if (p2.next == null) {
                    return pre.next;
                }
                p1 = p2.next;
                p2 = p2.next.next;
            } else {
                tmp = p1;
                p1 = p1.next;
                p2 = p2.next;
            }
            firstCircle=false;
        }
        return pre.next;
    }
}
